﻿#include "dataStruct.h"

//一.数组相关题目

//1.轮转数组 https://leetcode.cn/problems/rotate-array
//1.1 使用开辟一个相同大小数组存放数据翻转
void rotate(vector<int>& nums, int k) {
	int n = nums.size();
	vector<int>newArr(n);
	for (int i = 0; i < n; i++)
	{
		newArr[(i + k) % n] = nums[i];
	}
	nums.assign(newArr.begin(), newArr.end());
}

//1.2 先分别前一半与后一半，再反转整个数组
void reverse(vector<int>& nums, int begin, int end)
{
	while (begin < end)
	{
		swap(nums[begin++], nums[end--]);
	}
}
void rotate1(vector<int>& nums, int k) {
	k %= nums.size();
	reverse(nums, 0, nums.size() - k - 1);
	reverse(nums, nums.size() - k, nums.size() - 1);
	reverse(nums, 0, nums.size() - 1);
}


//2.删除有序数组中的重复项 https://leetcode.cn/problems/remove-duplicates-from-sorted-array
int removeDuplicates(vector<int>& nums) {
	int fast = 1, slow = 1;
	while (fast < nums.size())
	{
		if (nums[fast] != nums[fast - 1])
		{
			nums[slow] = nums[fast];
			slow++;
		}
		fast++;
	}
	return slow;
}


//3.数组形式的整数加法 https://leetcode.cn/problems/add-to-array-form-of-integer
vector<int> addToArrayForm(vector<int>& num, int k) {
	int tmp = 0;
	vector<int> v;
	for (int i = num.size() - 1; i >= 0; i--)
	{
		k += num[i];
		tmp = k % 10;
		v.push_back(tmp);
		k /= 10;
	}
	while (k)
	{
		tmp = k % 10;
		v.push_back(tmp);
		k /= 10;
	}
	reverse(v.begin(), v.end());
	return v;
}


//4.乘积最大子数组 https://leetcode.cn/problems/maximum-product-subarray/description/
int maxProduct(vector<int>& nums) {
	long long mx = nums[0];
	long long mn = nums[0];
	long long result = nums[0];
	for (int i = 1; i < nums.size(); i++)
	{
		if (nums[i] < 0)
		{
			swap(mx, mn);
		}
		mx = max((long long)nums[i], nums[i] * mx);
		mn = min((long long)nums[i], nums[i] * mn);
		if (mn < INT_MIN)
		{
			mn = nums[i];
		}
		result = max(mx, result);
	}
	return result;
}


//5.多数元素 https://leetcode.cn/problems/majority-element/description/
int majorityElement(vector<int>& nums) {
	unordered_map<int, int>count;
	int max = nums.size() / 2, maxNum = nums[0];
	for (auto it : nums)
	{
		if (++count[it] > max)
		{
			maxNum = it;
		}
	}
	return maxNum;
}
int majorityElement1(vector<int>& nums) {
	sort(nums.begin(), nums.end());
	return nums[nums.size() / 2];
}


//6.存在重复元素 https://leetcode.cn/problems/contains-duplicate/
bool containsDuplicate(vector<int>& nums) {
	sort(nums.begin(), nums.end());
	int left = 0, right = 1;
	while (right < nums.size())
	{
		if (nums[right] == nums[left])
		{
			return true;
		}
		else
		{
			left = right;
			right++;
		}
	}
	return false;
}


//7.搜索二维矩阵 https://leetcode.cn/problems/search-a-2d-matrix-ii/description/
bool searchMatrix(vector<vector<int>>& matrix, int target) {//起始位置很重要
	int i = 0;
	int j = matrix[i].size() - 1;
	while (i < matrix.size() && j >= 0)
	{
		if (matrix[i][j] > target)
		{
			j--;
		}
		else if (matrix[i][j] < target)
		{
			i++;
		}
		else
		{
			return true;
		}
	}
	return false;
}



//二.链表相关题目

//8.反转链表 https://leetcode.cn/problems/reverse-linked-list/description/
ListNode* reverseList(ListNode* head) {//我要操作哪个节点，哪个节点就作为判断的条件
	if (head == nullptr)
		return head;
	ListNode* cur = head;
	ListNode* next = cur->next;
	ListNode* prev = nullptr;
	while (cur)
	{
		cur->next = prev;

		prev = cur;
		cur = next;
		if (next != nullptr)
		{
			next = next->next;
		}
	}
	return prev;
}

//8.1优化方案 这边就是不直接关心三个指针，而是只对cur进行关心，其他的指针随着cur进行移动
ListNode* reverseList1(ListNode* head) {
	ListNode* prev = nullptr;
	ListNode* cur = head;
	ListNode* next = nullptr;
	while (cur)
	{
		next = cur->next;
		cur->next = prev;
		prev = cur;
		cur = next;
	}
	return prev;
}


//9.移除链表元素 https://leetcode.cn/problems/remove-linked-list-elements/description/
ListNode* removeElements(ListNode* head, int val) {//tip:删除节点时不需要将prev挪到cur，不删除时才需要prev只需要改变一次
	ListNode* cur = head;
	ListNode* next = nullptr;
	ListNode* prev = nullptr;
	while (cur)
	{
		next = cur->next;
		if (cur->val == val)
		{
			if (prev != nullptr)
			{
				prev->next = next;
			}
			if (cur == head)
			{
				head = next;
			}
			delete cur;
		}
		else
		{
			prev = cur;
		}
		cur = next;
	}
	return head;
}
//9.1创建一个头节点的优雅方式
ListNode* removeElements1(ListNode* head, int val) {
	ListNode* newHead = new ListNode;
	ListNode* cur = head;
	ListNode* tail = newHead;
	while (cur)
	{
		ListNode* next = cur->next;
		if (cur->val == val)
		{
			delete cur;
		}
		else
		{
			tail->next = cur;
			tail = cur;
			tail->next = nullptr;
		}
		cur = next;
	}
	return newHead->next;
}

//10.链表的中间结点 https://leetcode.cn/problems/middle-of-the-linked-list/description/
ListNode* middleNode(ListNode* head) {//快慢双指针方法
	ListNode* fast = head;
	ListNode* slow = head;
	while (fast && fast->next)
	{
		fast = fast->next->next;
		slow = slow->next;
	}
	return slow;
}

//11.删除链表的倒数第 N 个结点 https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
ListNode* removeNthFromEnd(ListNode* head, int n) {//两次遍历法
	//这里创建一个头节点非常重要，我们可以去除head前面为空的影响
	ListNode* newHead = new ListNode(0, head);
	ListNode* cur = head;
	int length = 0;
	while (cur)
	{
		ListNode* next = cur->next;
		cur = next;
		length++;
	}
	cur = newHead;
	for (int i = 1; i < length - n + 1; i++)
	{
		cur = cur->next;
	}
	ListNode* deleteNode = cur->next;
	cur->next = cur->next->next;
	delete deleteNode;
	return newHead->next;
}
//11.1双指针法
ListNode* removeNthFromEnd1(ListNode* head, int n) {
	//这里创建一个头节点非常重要，我们可以去除head前面为空的影响
	ListNode* newHead = new ListNode(0, head);
	ListNode* fast = newHead;
	ListNode* slow = newHead;
	for (int i = 0; i < n + 1; i++)
	{
		fast = fast->next;
	}
	while (fast)
	{
		fast = fast->next;
		slow = slow->next;
	}
	ListNode* deleteNode = slow->next;
	slow->next = slow->next->next;
	delete deleteNode;
	return newHead->next;
}

//12.合并两个有序链表 https://leetcode.cn/problems/merge-two-sorted-lists/description/
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
	ListNode* newHead = new ListNode;
	ListNode* cur = newHead;
	ListNode* node1 = list1;
	ListNode* node2 = list2;
	while (node1 || node2)
	{
		if (node2 == nullptr || node1 && node1->val <= node2->val)
		{
			cur->next = node1;
			node1 = node1->next;
			cur = cur->next;
			cur->next = nullptr;
		}
		else
		{
			cur->next = node2;
			node2 = node2->next;
			cur = cur->next;
			cur->next = nullptr;
		}
	}
	return newHead->next;
}
//12.1 优化一下代码逻辑，在判断的地方，我们判断太复杂了，可以当只要有一个链表为空就可以把另一条剩下的挂上去
ListNode* mergeTwoLists1(ListNode* list1, ListNode* list2) {
	ListNode* newHead = new ListNode;
	ListNode* cur = newHead;
	while (list1 && list2)
	{
		if (list1->val <= list2->val)
		{
			cur->next = list1;
			list1 = list1->next;
		}
		else
		{
			cur->next = list2;
			list2 = list2->next;
		}
		cur = cur->next;
		cur->next = nullptr;
	}
	list1 ? cur->next = list1 : cur->next = list2;
	return newHead->next;
}


//13.回文链表 https://leetcode.cn/problems/aMhZSa/description/
bool isPalindrome(ListNode* head) {//栈方式
	ListNode* cur = head;
	stack<ListNode*> s;
	while (cur)
	{
		s.push(cur);
		cur = cur->next;
	}
	cur = head;
	while (!s.empty())
	{
		if (s.top()->val != cur->val)
			return false;
		s.pop();
		cur = cur->next;
	}
	return true;
}	
//13.1快慢双指针+反转链表方法
bool isPalindrome1(ListNode* head) {
	// 用快慢指针找中点（不需要计算长度）
	ListNode* slow = head;
	ListNode* fast = head;

	while (fast->next && fast->next->next) {
		slow = slow->next;
		fast = fast->next->next;
	}
	ListNode* head1 = slow->next;

	head1 = reverse_isPalindrome1(head1);

	ListNode* cur = head;
	ListNode* cur1 = head1;
	while (cur1)
	{
		if (cur1->val != cur->val)
			return false;
		cur1 = cur1->next;
		cur = cur->next;
	}

	reverse_isPalindrome1(head1);
	return true;
}
ListNode* reverse_isPalindrome1(ListNode* cur)
{
	ListNode* prev = nullptr;
	while (cur)
	{
		ListNode* next = cur->next;
		cur->next = prev;
		prev = cur;
		cur = next;
	}
	return prev;
}


//14.相交链表 https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
	unordered_set<ListNode*>s;
	ListNode* cur = headA;
	while (cur)
	{
		s.insert(cur);
		cur = cur->next;
	}
	cur = headB;
	while (cur)
	{
		if (s.count(cur))
			return cur;
		cur = cur->next;
	}
	return nullptr;
}
//14.1双指针算法
ListNode* getIntersectionNode1(ListNode* headA, ListNode* headB) {
	ListNode* pa = headA;
	ListNode* pb = headB;
	while (pa != pb)
	{
		if (pa != nullptr)
			pa = pa->next;
		else
			pa = headB;

		if (pb != nullptr)
			pb = pb->next;
		else
			pb = headA;
	}
	return pa;
}


//15.环形链表 https://leetcode.cn/problems/linked-list-cycle/description/
bool hasCycle(ListNode* head) {//快慢双指针
	ListNode* fast = head;
	ListNode* slow = head;
	while (fast && fast->next)
	{
		fast = fast->next->next;
		slow = slow->next;
		if (fast == slow)
			return true;
	}
	return false;
}


//16.随机链表的复制 https://leetcode.cn/problems/copy-list-with-random-pointer/description/
Node* copyRandomList(Node* head) {
	Node* cur = head;
	Node* newHead = new Node(-1);
	Node* tail = newHead;
	unordered_map<Node*, Node*>m;
	while (cur)
	{
		Node* newNode;
		if (!m.count(cur))
		{
			newNode = new Node(cur->val);
			m.insert(make_pair(cur, newNode));
		}
		else
		{
			newNode = m.find(cur)->second;
		}

		tail->next = newNode;
		tail = newNode;
		if (!m.count(cur->random) && cur->random)
		{
			newNode = new Node(cur->random->val);
			m.insert(make_pair(cur->random, newNode));
		}
		if (cur->random)
			tail->random = m[cur->random];

		cur = cur->next;
	}
	return newHead->next;
}
//16.1优化思路，两趟分开走，先复制val再复制random
Node* copyRandomList1(Node* head) {
	Node* cur = head;
	Node* newHead = new Node(-1);
	Node* tail = newHead;
	unordered_map<Node*, Node*>m;
	while (cur)
	{
		Node* newNode = new Node(cur->val);
		m.insert(make_pair(cur, newNode));
		tail->next = newNode;
		tail = newNode;

		cur = cur->next;
	}
	cur = head;
	while (cur)
	{
		if (cur->random)
			m[cur]->random = m[cur->random];
		cur = cur->next;
	}
	return newHead->next;
}



//三、栈和队列相关题目

//17.有效的括号 https://leetcode.cn/problems/valid-parentheses/description/
bool isValid(string s) {//算法可以优化，主要是注意单个括号的情况
	stack<char>st;
	for (auto it : s)
	{
		if (it == '(' || it == '[' || it == '{')
		{
			st.push(it);
		}
		else
		{
			if (st.empty())
				return false;
			char top = st.top();
			switch (it)
			{
			case (')'):
				if (top != '(')
					return false;
				break;
			case (']'):
				if (top != '[')
					return false;
				break;
			case ('}'):
				if (top != '{')
					return false;
				break;
			}
			st.pop();
		}
	}
	if (!st.empty())
		return false;
	return true;
}


//18.用队列实现栈 https://leetcode.cn/problems/implement-stack-using-queues/description/
class MyStack {//队列是获取队头是front接口不是top，还有stack与queue是没有迭代器的
public:
	MyStack() {

	}

	void push(int x) {
		if (_q1.empty())
		{
			_q1.push(x);
			while (!_q2.empty())
			{
				_q1.push(_q2.front());
				_q2.pop();
			}
		}
		else
		{
			_q2.push(x);
			while (!_q1.empty())
			{
				_q2.push(_q1.front());
				_q1.pop();
			}
		}
	}

	int pop() {
		queue<int>* q = _q1.empty() ? &_q2 : &_q1;
		int front = q->front();
		q->pop();
		return front;
	}

	int top() {
		queue<int>* q = _q1.empty() ? &_q2 : &_q1;
		return q->front();
	}

	bool empty() {
		return _q1.empty() && _q2.empty();
	}

	void test()
	{
		//用来测试的函数
	}
private:
	queue<int> _q1;
	queue<int> _q2;
};


//19.设计循环队列 https://leetcode.cn/problems/design-circular-queue/description/
class MyCircularQueue {
private:
	stack<int> _s1;
	stack<int> _s2;
	int _size;
	int _capacity;
	int _tail;
public:
	MyCircularQueue(int k) :_size(0), _capacity(k), _tail(-1) {
	}

	int getPopVal(stack<int>& s)
	{
		int top = s.top();
		s.pop();
		return top;
	}

	bool enQueue(int value) {
		if (_size == _capacity)
			return false;
		_size++;
		if (_s1.empty())
		{
			while (!_s2.empty())
			{
				_s1.push(getPopVal(_s2));
			}
			_s1.push(value);
			_tail = value;
			while (!_s1.empty())
			{
				_s2.push(getPopVal(_s1));
			}
		}
		else
		{
			while (!_s1.empty())
			{
				_s2.push(getPopVal(_s1));
			}
			_s2.push(value);
			_tail = value;
			while (!_s2.empty())
			{
				_s1.push(getPopVal(_s2));
			}
		}
		return true;
	}

	bool deQueue() {
		if (_size <= 0)
			return false;
		_size--;
		stack<int>& s = _s1.empty() ? _s2 : _s1;
		s.pop();
		if (_size == 0)
			_tail = -1;
		return true;
	}

	int Front() {
		if (_size <= 0)
			return -1;
		stack<int>& s = _s1.empty() ? _s2 : _s1;
		return s.top();
	}

	int Rear() {
		return _tail;
	}

	bool isEmpty() {
		return _size == 0;
	}

	bool isFull() {
		return _size == _capacity;
	}
};
//19.1 使用数组模拟循环队列，空一个位置来区分空和满队列
class MyCircularQueue1 {
private:
	vector<int> _v;
	int _front = 1;
	int _rear = 1;
public:
	MyCircularQueue1(int k) :_v(k + 1, -1) {
	}

	bool enQueue(int value) {
		if (((_rear + 1) % _v.size()) == _front)
			return false;
		_v[_rear++] = value;
		_rear %= _v.size();
		return true;
	}

	bool deQueue() {
		if (_front == _rear)
			return false;
		_front++;
		_front %= _v.size();
		return true;
	}

	int Front() {
		if (isEmpty())
			return -1;
		return _v[_front];
	}

	int Rear() {
		if (isEmpty())
			return -1;
		int pos = _rear - 1;
		if (pos == -1)
			pos = _v.size() - 1;
		return _v[pos];
	}

	bool isEmpty() {
		return _rear == _front;
	}

	bool isFull() {
		return ((_rear + 1) % _v.size()) == _front;
	}
};


//20.最小栈 https://leetcode.cn/problems/min-stack/
class MinStack {//两个栈即可解决
private:
	stack<int>_s;
	stack<int>_min;
	int _minVal = -1;
public:
	MinStack() {
	}

	void push(int val) {
		if (_min.empty())
			_min.push(val);
		else
			_min.push(val < _min.top() ? val : _min.top());
		_s.push(val);
	}

	void pop() {
		_min.pop();
		_s.pop();
	}

	int top() {
		return _s.top();
	}

	int getMin() {
		return _min.top();
	}
};


//21.验证栈序列 https://leetcode.cn/problems/validate-stack-sequences/description/
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
	stack<int>s;
	int pos = 0;
	for (int i = 0; i < pushed.size(); i++)
	{
		s.push(pushed[i]);
		while (!s.empty() && s.top() == popped[pos])
		{
			pos++;
			s.pop();
		}
	}
	if (s.empty())
		return true;
	else
		return false;
}



//四、树相关题目

//22.二叉树的前序遍历 https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
class Solution_preorderTraversal { //递归解法
private:
	vector<int> v;
public:
	void traversal(TreeNode* node)
	{
		if (node == nullptr)
			return;
		v.push_back(node->val);
		traversal(node->left);
		traversal(node->right);
	}
	vector<int> preorderTraversal(TreeNode* root) {
		traversal(root);
		return v;
	}
};
//22.1 迭代解法
vector<int> preorderTraversal(TreeNode* root) {
	TreeNode* node = root;
	stack<TreeNode*> s;
	vector<int> v;
	while (node != nullptr || !s.empty())
	{
		while (node != nullptr)
		{
			v.push_back(node->val);
			s.push(node);
			node = node->left;
		}
		TreeNode* top = s.top();
		s.pop();
		node = top->right;
	}
	return v;
}


//23.二叉树的中序遍历 https://leetcode.cn/problems/binary-tree-inorder-traversal/description/
class Solution_inorderTraversal {
private:
	vector<int> v;
public:
	void traversal(TreeNode* node)
	{
		if (node == nullptr)
			return;
		traversal(node->left);
		v.push_back(node->val);
		traversal(node->right);
	}
	vector<int> inorderTraversal(TreeNode* root) {
		traversal(root);
		return v;
	}
};
//23.1 迭代解法
vector<int> inorderTraversal(TreeNode* root) {
	stack<TreeNode*>s;
	vector<int> v;
	TreeNode* node = root;
	while (node != nullptr || !s.empty())
	{
		while (node != nullptr)
		{
			s.push(node);
			node = node->left;
		}
		TreeNode* top = s.top();
		s.pop();
		v.push_back(top->val);
		node = top->right;
	}
	return v;
}


//24.二叉树的后序遍历 https://leetcode.cn/problems/binary-tree-postorder-traversal/description/
class Solution_postorderTraversal {
private:
	vector<int> v;
public:
	void traversal(TreeNode* node)
	{
		if (node == nullptr)
			return;
		traversal(node->left);
		traversal(node->right);
		v.push_back(node->val);
	}
	vector<int> postorderTraversal(TreeNode* root) {
		traversal(root);
		return v;
	}
};
//24.1 迭代写法
vector<int> postorderTraversal(TreeNode* root) {//注意还得复习一下这种解法，还是不太熟练
	stack<TreeNode*>s;
	vector<int> v;
	TreeNode* node = root;
	TreeNode* prev = nullptr;
	while (node != nullptr || !s.empty())
	{
		while (node != nullptr)
		{
			s.push(node);
			node = node->left;
		}
		node = s.top();
		if ((node->right == nullptr) || (prev == node->right))
		{
			v.push_back(node->val);
			prev = node;
			s.pop();
			node = nullptr;
		}
		else
		{
			node = node->right;
		}
	}
	return v;
}


//25.二叉树构建与遍历 https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpld=60&&tqld=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking
class buildBinaryTreeAndInorderTraversal
{
	vector<char> v;

	struct TreeNode {
		TreeNode* _left = nullptr;
		TreeNode* _right = nullptr;
		int _val = 0;
	};

	int pos = 0;
	TreeNode* traverse(TreeNode* node)
	{
		if (v[pos] == '#')
		{
			pos++;
			return nullptr;
		}
		node = new TreeNode;

		node->_val = v[pos++];
		node->_left = traverse(node->_left);
		node->_right = traverse(node->_right);
		return node;
	}

	void traverseMid(TreeNode* node)
	{
		if (node == nullptr)
			return;
		traverseMid(node->_left);
		printf("%c ", node->_val);
		traverseMid(node->_right);
	}

	void test() {
		char x;
		while ((scanf("%c", &x)) != EOF)
		{
			v.push_back(x);
		}
		TreeNode* root;
		root = traverse(root);
		traverseMid(root);
	}
};


//26.平衡二叉树 https://leetcode.cn/problems/balanced-binary-tree/description/
class Solution_isBalanced {
public:
	int getDeep(TreeNode* node)
	{
		if (node == nullptr)
			return 0;
		int deep1 = getDeep(node->left);
		int deep2 = getDeep(node->right);
		return deep1 > deep2 ? deep1 + 1 : deep2 + 1;
	}
	bool _isBalanced(TreeNode* node)
	{
		if (node == nullptr)
		{
			return true;
		}

		bool flag = abs(getDeep(node->left) - getDeep(node->right)) <= 1;
		return flag && _isBalanced(node->left) && _isBalanced(node->right);
	}

	bool isBalanced(TreeNode* root) {
		return _isBalanced(root);
	}
};


//27.相同的树 https://leetcode.cn/problems/same-tree/description/
class Solution_isSameTree {
public:
	bool traverse(TreeNode* node1, TreeNode* node2)
	{
		if (node1 == nullptr && node2 == nullptr)
			return true;
		if (node1 == nullptr && node2 != nullptr || node1 != nullptr && node2 == nullptr)
			return false;

		bool flag = (node1->val == node2->val);
		return flag && traverse(node1->left, node2->left)\
			&& traverse(node1->right, node2->right);
	}
	bool isSameTree(TreeNode* p, TreeNode* q) {
		return traverse(p, q);
	}
};


//28.翻转二叉树 https://leetcode.cn/problems/invert-binary-tree/description/
class Solution_invertTree {
public:
	void traverse(TreeNode* node)
	{
		if (node == nullptr)
			return;
		swap(node->left, node->right);
		traverse(node->left);
		traverse(node->right);
	}
	TreeNode* invertTree(TreeNode* root) {
		traverse(root);
		return root;
	}
};


//29.二叉树的层序遍历 https://leetcode.cn/problems/binary-tree-level-order-traversal/description/
class Solution_levelOrder {//DFS深度优先解法
public:
	vector<vector<int>>v;
	void traverse(TreeNode* node, int level)
	{
		if (node == nullptr)
			return;
		if (level >= v.size()) v.resize(level + 1);
		v[level].push_back(node->val);
		traverse(node->left, level + 1);
		traverse(node->right, level + 1);
	}
	vector<vector<int>> levelOrder(TreeNode* root) {
		traverse(root, 0);
		return v;
	}
};
//29.1 BFS广度优先解法
class Solution_levelOrder1 {
public:
	vector<vector<int>> v;
	queue<TreeNode*> q;
	vector<vector<int>> levelOrder(TreeNode* root) {
		if (root) q.push(root);
		while (!q.empty())
		{
			int n = q.size();//每一次开始都只有一层节点在队列中
			vector<int>v1;
			for (int i = 0; i < n; i++)
			{
				TreeNode* front = q.front();
				v1.push_back(front->val);
				q.pop();
				if (front->left)q.push(front->left);
				if (front->right)q.push(front->right);
			}
			v.push_back(v1);
		}
		return v;
	}
};


//30.二叉树的最近公共祖先 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
class Solution_lowestCommonAncestor {//我这样写时间复杂度很高，需要优化
public:
	TreeNode* pnode = nullptr;
	TreeNode* node1;
	TreeNode* node2;
	int flag = 0;
	int traverse_count(TreeNode* node)
	{
		if (node == nullptr)
			return 0;
		int tmp = 0;
		if (node->val == node1->val || node->val == node2->val)
			tmp = 1;
		return tmp + traverse_count(node->left) + traverse_count(node->right);
	}
	void traverse(TreeNode* node)
	{
		if (node == nullptr)
			return;
		traverse(node->left);
		traverse(node->right);
		if (traverse_count(node) == 2 && flag == 0)
		{
			pnode = node;
			flag = 1;
		}
	}
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		node1 = p;
		node2 = q;
		traverse(root);
		return pnode;
	}
};
//30.1 优化一下思路不需要遍历第二次检查子节点是否为一个公共父节点，只需要边遍历边检查
class Solution_lowestCommonAncestor1 {
public:
	TreeNode* pnode = nullptr;
	TreeNode* node1;
	TreeNode* node2;
	int flag = 0;
	int traverse_count(TreeNode* node)
	{
		if (node == nullptr)
			return 0;
		int tmp = 0;
		if (node->val == node1->val || node->val == node2->val)
			tmp = 1;
		tmp = tmp + traverse_count(node->left) + traverse_count(node->right);
		if (tmp == 2 && flag == 0)
		{
			pnode = node;
			flag = 1;
		}
		return tmp;
	}

	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		node1 = p;
		node2 = q;
		traverse_count(root);
		return pnode;
	}
};
//30.2优雅且好理解的方式
class Solution_lowestCommonAncestor2 {
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		// 递归终止条件
		if (root == nullptr) return nullptr;

		//关键1：如果当前节点是 p 或 q，直接返回
		if (root == p || root == q) return root;

		//关键2：在左右子树中查找
		TreeNode* left = lowestCommonAncestor(root->left, p, q);
		TreeNode* right = lowestCommonAncestor(root->right, p, q);

		//关键3：根据左右子树的返回值判断
		if (left != nullptr && right != nullptr) {
			// 左右都找到了 → 当前节点就是最近公共祖先
			return root;
		}

		// 只有一边找到，返回找到的那边
		// 如果都没找到，返回 nullptr
		return left != nullptr ? left : right;
	}
};


//31.二叉搜索树与双向链表 https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpld=13&&tqld=11179&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
class Solution_Convert {
public:
	TreeNode* head = nullptr;
	TreeNode* prev = nullptr;
	void traverse(TreeNode* node)
	{
		if (node == nullptr)
			return;
		traverse(node->left);
		if (head == nullptr) {
			head = node;
			prev = node;
		}
		else {
			node->left = prev;
			prev->right = node;
			prev = node;
		}
		traverse(node->right);
	}
	TreeNode* Convert(TreeNode* pRootOfTree) {
		traverse(pRootOfTree);
		return head;
	}
};


//32.从前序与中序遍历序列构造二叉树 https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/
class Solution_buildTree {
public:
	unordered_map<int, int> m;
	TreeNode* createTree(vector<int>& preorder, vector<int>& inorder, \
		int p_left, int p_right, int i_left, int i_right)
	{
		if (i_left > i_right)
			return nullptr;
		int i_root = m[preorder[p_left]];//获得中序中根节点位置
		TreeNode* node = new TreeNode(preorder[p_left]);

		int leftTreeSize = i_root - i_left;
		node->left = createTree(preorder, inorder, p_left + 1, p_left + leftTreeSize, i_left, i_root - 1);
		node->right = createTree(preorder, inorder, p_left + 1 + leftTreeSize, p_right, i_root + 1, i_right);

		return node;
	}
	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
		int i = 0;
		for (auto it : inorder)
		{
			m.insert(make_pair(it, i++));
		}
		return createTree(preorder, inorder, 0, preorder.size() - 1, 0, preorder.size() - 1);

	}
};